W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
W Bajtocji jest miast (ponumerowanych liczbami od do ). Miasta są połączone dwukierunkowymi drogami. Ponieważ król Bajtocji nie jest zbyt skory do inwestycji w rozbudowę dróg, jest ich zaledwie . Można jednak przy ich pomocy dotrzeć z dowolnego miasta do dowolnego innego miasta.
Pewnego dnia, podróżnik Bajtazar zawitał do miasta o numerze . Zamierza on odwiedzić jeszcze miasta , , ..., (niekoniecznie w tej kolejności) - liczby są parami różne i wszystkie są różne od . Bajtazarowi powoli kończą się fundusze przeznaczone na podróż, dlatego chciałby objechać wszystkie zaplanowane miasta za pomocą możliwie najkrótszej trasy (zaczynającej się w mieście ). Przez trasę rozumiemy ciąg jednej lub więcej dróg, w którym początek następnej drogi jest końcem poprzedniej. Pomóż Bajtazarowi wyznaczyć długość najkrótszej trasy odwiedzającej wybrane przez niego miasta.
Napisz program, który:
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i oddzielone pojedynczym odstępem (, ), gdzie jest liczbą miast w Bajtocji, a - numerem miasta, w którym znajduje się Bajtazar.
Każdy z kolejnych wierszy opisuje jedną z dróg Bajtocji. Wiersz -szy (dla ) zawiera trzy liczby całkowite , i oddzielone pojedynczymi odstępami (, ), i są miastami połączonymi drogą, a jest długością drogi. Wiersz -szy zawiera pojedynczą liczbę całkowitą - liczbę miast, które Bajtazar chciałby odwiedzić (). Kolejny wiersz zawiera różnych liczb całkowitych oddzielonych pojedynczymi odstępami - są to numery miast wybranych przez Bajtazara (, ).
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać pojedynczą liczbę całkowitą - długość najkrótszej trasy Bajtazara.
Dla danych wejściowych:
4 2 1 2 1 4 2 2 2 3 3 2 1 3
poprawną odpowiedzią jest:
5
Autor zadania: Jakub Radoszewski.